package cn.xuchunh.dp.backpack;

/**
 * 完全背包问题
 *
 * 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价格是w[i].
 * 求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大
 *
 * dp[i][v] = max{dp[i-1][v - k * c[i]] + k * w[i] | 0 <= k * c[i]<= v}
 *
 * @author yehui
 * @date 2021/2/9
 */
public class CompleteBackpack {

    /**
     * 根据递推公式
     *
     * @param V
     * @param C
     * @param W
     * @return
     */
    public int normal(int V, int[] C, int[] W) {
        int[][] dp = new int[C.length + 1][V + 1];

        for (int i = 1; i <= C.length; i++) {
            for (int j = 1; j <= V; j++) {
                for (int k = 0; k * C[i - 1] <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * C[i - 1]] + k * W[i - 1]);
                }
            }
        }

        return dp[C.length][V];
    }

    public int optSpace(int V, int[] C, int[] W) {
        int[] dp = new int[V + 1];
        for (int i = 0; i < C.length; i++) {
            for (int j = C[i]; j <= V; j++) {
                dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
            }
        }

        return dp[V];
    }

}
